package com.nju.sorts;

public class QuickSort {
	public static void main(String[] args) {
		int data[] = { 2, 7, 5, 3, 8, 6, 4 };
		QuickSort sort = new QuickSort();
		// sort.quickSortByThreeMedium(data, 0, data.length - 1);
		sort.quickSort(data, 0, data.length - 1);
		sort.show(data);
	}

	/**
	 * 普通快排，即Hoare快排
	 * 
	 * @param data
	 * @param low
	 * @param high
	 */
	public void quickSort(int data[], int low, int high) {
		if (low < high) {
			int privot = this.partition(data, low, high);
			this.quickSort(data, low, privot - 1);
			this.quickSort(data, privot + 1, high);
		}
	}

	/**
	 * HOARE快排划分，就地重排，每次都以第一个元素为主元
	 * 
	 * @param data
	 * @param low
	 * @param high
	 * @return
	 */
	public int partition(int data[], int low, int high) {
		int key = data[low];
		while (low < high) {
			while (data[high] > key && low < high) {
				high--;
			}
			if (low < high) {
				data[low] = data[high];
				low++;
			}
			while (data[low] < key && low < high) {
				low++;
			}
			if (low < high) {
				data[high] = data[low];
				high--;
			}
		}

		data[high] = key;
		return high;
	}

	/**
	 * 采用三分中值法的快排
	 * 
	 * @param data
	 * @param low
	 *            首位
	 * @param high
	 *            末位
	 */
	public void quickSortByThreeMedium(int data[], int low, int high) {
		if (low < high) {
			int privot = this.partitionByThreeMedium(data, low, high);
			this.quickSortByThreeMedium(data, low, privot - 1);
			this.quickSortByThreeMedium(data, privot + 1, high);
		}
	}

	/**
	 * 采用三分中值法的N.Lomuto快排划分，就地重排
	 * 
	 * @param data
	 * @param low
	 * @param high
	 * @return
	 */
	public int partitionByThreeMedium(int data[], int low, int high) {
		int m = (low + high) / 2;
		if (data[m] < data[low]) {
			swap(data, low, m);
		}
		if (data[high] < data[low]) {
			swap(data, low, high);
		}
		if (data[m] < data[high]) {
			swap(data, m, high);
		}

		int i = low - 1;
		int j = low;
		int key = data[high];

		while (j < high) {
			if (data[j] < key) {
				i++;
				swap(data, i, j);
			}
			j++;
		}

		swap(data, i + 1, high);
		return i + 1;
	}

	private static void swap(int data[], int a, int b) {
		int temp = data[a];
		data[a] = data[b];
		data[b] = temp;
	}

	private void show(int data[]) {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i] + " ");
		}
	}
}
